class Solution {
public:
    string decodeString(string s) {
        stack<int> digitst;
        stack<string> stringst;
        stringst.push("");
        int i = 0;
        int n = s.size();
        while (i < n) {
            if (s[i] >= '0' && s[i] <= '9') {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9') {
                    tmp = tmp * 10 + s[i] - '0';
                    ++i;
                }
                digitst.push(tmp);
            } else if (s[i] == '[') {
                string tmp = "";
                ++i;
                while (s[i] >= 'a' && s[i] <= 'z') {
                    tmp += s[i];
                    ++i;
                }
                stringst.push(tmp);
            } else if (s[i] == ']') {
                int num = digitst.top();
                digitst.pop();
                string p = stringst.top();
                stringst.pop();
                while (num--) {
                    stringst.top() += p;
                }
                ++i;
            } else {
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z') {
                    tmp += s[i];
                    ++i;
                }
                stringst.top() += tmp;
            }
        }

        return stringst.top();
    }
};